package sort.mergeSort;

import org.junit.Test;
import sort.util.SortUtil;

public class util {
    @Test
    public void test() {
        Integer[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
//        Integer[] nums = {3, 1, 2};
        assist = new Comparable[nums.length]; //辅助数组 存放排序结果的
        sort(nums, 0, nums.length-1);
        SortUtil.display(nums);
    }

    Comparable[] assist;    //声明为全局引用
    public void sort(Comparable[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;    //这里的end要设置为length-1,不然 /2 这个操作就会有问题
        sort(nums, start, mid);       //左边进行归并
        sort(nums, mid + 1, end);//右边进行归并
        merge(nums, start, mid, end); //合并
    }

    //将两个有序子数组进行合并
    public void merge(Comparable[] nums, int start, int mid, int end) {
        int left = start;       //指向第一组的第一个元素
        int right = mid + 1;    //指向第二组的第一个元素
        int p = start;          //assist的指针
        while (left <= mid && right <= end) {
            if (SortUtil.greater(nums[left], nums[right])) {
                assist[p++] = nums[right++];
            }else {
                assist[p++] = nums[left++];
            }
        }

        while (left <= mid) {   //若第一组还有剩余直接填充到末尾
            assist[p++] = nums[left++];
        }
        while (right <= end) {   //若第二组还有剩余直接填充到末尾
            assist[p++] = nums[right++];
        }

        for (int i = start; i <= end; i++) {
            nums[i] = assist[i];
        }
    }



}
